RANGE = 1001
MOD = 10 ** 9 + 7

# 定义和状态矩阵：dp[n][k]=长度为n，逆序对个数为k的方案数
DP = [[0] * RANGE for _ in range(RANGE)]

# 当k=0时：dp[i][k]=0
for i in range(1, RANGE):
    DP[i][0] = 1

# 非前缀和状态转移公式 dp[i][j] = sum(dp[i-1][0],...,dp[i-1][j])

for i in range(2, RANGE):
    now = DP[i - 1][0]
    for j in range(1, RANGE):
        now += DP[i - 1][j]
        if j >= i:
            now -= DP[i - 1][j - i]
        DP[i][j] = now % MOD


class Solution:
    def kInversePairs(self, n: int, k: int) -> int:
        return DP[n][k]


if __name__ == "__main__":
    print(Solution().kInversePairs(3, 0))  # 1
    print(Solution().kInversePairs(3, 1))  # 2

    # 测试用例14/80
    print(Solution().kInversePairs(3, 3))  # 1
